package fun.ticsmyc.question;

import org.junit.Test;

/**
 * https://ac.nowcoder.com/acm/contest/9246/C
 *
 */
public class 根据DFS序获取二叉树层级关系 {

    @Test
    public void test(){
        int[] arr=  new int[]{1,2,3,4,5};
        System.out.println(tree6(2,arr));
    }


    /**
     *
     * @param k k叉树
     * @param a 先序遍历序列
     * @return
     */
    int dfsPos =0;
    long res =0;
    public long tree6 (int k, int[] a) {

        fun(k,a,0);
        return res;
    }

    public void fun(int k,int[] a,long bfsPos){
        if(bfsPos >= a.length || dfsPos>=a.length){
            return;
        }
        int cur = a[dfsPos];
        for(int i=1;i<=k;++i){
            //k个子节点
            if(bfsPos*k+i <a.length){
                int child = a[++dfsPos];
                res += (cur ^ child);
                fun(k,a,bfsPos*k+i);
            }else{
                break;
            }
        }

    }
}
